package com.zhangxiaofanfan.hotcode.fourth.third;


/**
 * <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked">33. 搜索旋转排序数组</a>
 *
 * @date 2024-06-29 03:21:25
 * @author zhangxiaofanfan
 */
public class HotCode066 {
    public static void main(String[] args) {
        HotCode066 hotCode = new HotCode066();
        int[] nums = {3, 1};
        System.out.println(hotCode.search(nums, 1));
    }

    public int search(int[] nums, int target) {
        int k = 0;
        if (nums[0] > nums[nums.length - 1]) {
            // 表示数组有旋转, 需要转出旋转因子
            int left = 0, right = nums.length - 1, mid;
            while (left < right) {
                mid = left + ((right - left) >> 1);
                if (nums[mid] >= nums[0]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            k = left;
        }
        if (target < nums[k] || target > nums[(nums.length + k - 1) % nums.length]) {
            return -1;
        }
        int left = 0, right = nums.length - 1, mid, readIndex;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            readIndex = (mid + k) % nums.length;
            if (nums[readIndex] == target) {
                return readIndex;
            } else if (nums[readIndex] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

}
